package com.ycsyxt.guide;

/**
 * @author ycs(15241496739 @ 163.com)
 * @date 2022/6/12
 **/
public class Class11 {
    // 构建前缀数
    public static void main(String[] args) {
        String a = "hello";
        String b = "world";
        String c = "wol";
        String d = "hi";
        Main main = new Main();
        main.insert(a);
        main.insert(b);
        main.insert(d);
        System.out.println(main.search(a));
        System.out.println(main.search(b));
        System.out.println(main.search(c));
        System.out.println(main.search(d));
    }
}

class TreeNode {
    public TreeNode[] children;

    public boolean isEnd;

    public TreeNode() {
        isEnd = false;
        children = new TreeNode[26];
    }
}

class Main {
    private TreeNode root = new TreeNode();

    public void insert(String key) {
        TreeNode newNode = root;
        int index;

        for (char ch : key.toCharArray()) {
            index = ch - 'a';
            if (newNode.children[index] == null) {
                newNode.children[index] = new TreeNode();
            }
            newNode = newNode.children[index];
        }
        newNode.isEnd = true;
    }

    public boolean search(String key) {
        TreeNode searchNode = root;
        int index;

        for (char ch : key.toCharArray()) {
            index = ch - 'a';
            if (searchNode.children[index] == null) {
                return false;
            }
            searchNode = searchNode.children[index];
        }

        return searchNode != null && searchNode.isEnd;
    }
}
